package com.ctrip.demo.leetcode;

import java.util.Arrays;

public class LeetCode2055 {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new LeetCode2055().platesBetweenCandles("**|**|***|", new int[][]{{2, 5}, {5, 9}})));
    }



    public int[] platesBetweenCandles(String s, int[][] qs) {

        int[] res = new int[qs.length];
        // 前缀数组
        int[] nextCandleIdx = getNextCandleIdx(s);
        int[] prevCandleIdx = getPrevCandleIdx(s);
        int[] plateCnt = getPlateCnt(s);

        for(int i = 0; i < qs.length; i ++) {
            int formerIdx = nextCandleIdx[qs[i][0]];
            int latterIdx = prevCandleIdx[qs[i][1]];

            if (formerIdx == -1 || latterIdx == -1 || formerIdx >latterIdx) {
                res[i] = 0;
            } else {
                res[i] = plateCnt[latterIdx] - plateCnt[formerIdx];
            }
        }

        return res;
    }

    private int[] getPlateCnt(String s) {
        int length = s.length();
        int[] res = new int[length];
        for(int i = 0; i < length; i++) {
            res[i] += i == 0 ? 0 : res[i - 1];
            if (s.charAt(i) == '*') {
                res[i] ++;
            }
        }
        return res;
    }

    private int[] getNextCandleIdx(String s) {
        int length = s.length();
        int[] res = new int[length];
        int lastIdx = -1;
        for(int i = length - 1; i >= 0; i--) {
            if (s.charAt(i) == '|') {
                lastIdx = i;
            }
            res[i] = lastIdx;
        }
        return res;
    }

    private int[] getPrevCandleIdx(String s) {
        int length = s.length();
        int[] res = new int[length];
        int lastIdx = -1;
        for(int i = 0; i < length; i++) {
            if (s.charAt(i) == '|') {
                lastIdx = i;
            }
            res[i] = lastIdx;
        }
        return res;
    }

}
